// leetcode 349
// 给定两个数组，编写一个函数来计算它们的交集。
// 输入：nums1 = [1,2,2,1], nums2 = [2,2]
// 输出：[2]

// 解题思路
// 1，求nums1 和 nums2都有值
// 2，用字典建立一个映射关系，记录nums1里有的值
// 3，遍历nums2, 找出nums1里也有的值

// 解题步骤
// 1，新建一个字典，遍历nums1，填充字典
// 2，遍历nums2,遇到字典里的值就选出，并从字典中删除

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function (nums1, nums2) {
  const map = new Map()
  nums1.forEach(n => {
    map.set(n, true)
  })

  const res = []
  nums2.forEach(n => {
    if (map.get(n)) {
      res.push(n)
      map.delete(n)
    }
  })
  return res
};

// 时间复杂度： O(m+n)
// 空间复杂度：O(m)


// leetcode 1
/**
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

*/

// 输入：nums = [2,7,11,15], target = 9
// 输出：[0,1]
// 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

// 解题思路
// 1，把nums想象成为相亲者
// 2，把target想象成匹配条件
// 3，用字典建立一个婚姻介绍所，存储相亲这的数字和下标

// 解题步骤
// 1，新建一个字典
// 2，遍历nums
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  const map = new Map()
  for (let i = 0; i < nums.length; i++) {
    const n = nums[i]
    const n2 = target - n
    if (map.has(n2)) {
      return [map.get(n2), i]
    } else {
      map.set(n, i)
    }
  }
};

// 时间复杂度：O(n)
// 空间复杂度：O(n)

/**
 * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
 * 输入: s = "abcabcbb"
   输出: 3
   解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 */

// 解题思路
// 1，先找出所有的不包含重复字符的子串
// 2，找出长度最大那个子串，返回其长度即可

// 解题步骤
// 1，用双指针维护一个滑动窗口，用来剪切子串
// 2，不断移动右指针，遇到重复字符，就把左指针移动到重复字符的下一位
// 3，过程中，记录所有窗口的长度，并返回最大值

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  let l = 0 // 左指针
  let res = 0 // 声明res 记录最大值
  const map = new Map()
  for (let r = 0; r < s.length; r++) {  // 右指针滑动遍历
    if (map.has(s[r]) && map.get(s[r]) >= l) { // map.get(s[r]) >= l 尾元素与首与首元素相同的情况
      l = map.get(s[r]) + 1
    }
    res = Math.max(res, r - l + 1)
    map.set(s[r], r)
  }
  return res
};

// 时间复杂度：O(n)
// 空间复杂度：O(m),m是字符串中不重复字符的个数


// leetcode 76
// 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

// 注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

// 解题思路
// 1，先找出所有的包含T的子串
// 2，找出长度最小那个子串，返回即可

// 解题步骤
// 1，用双指针维护一个滑动窗口，用来维护所有的滑动子串
// 2，移动右指针，找到包含T的子串，移动指针，尽量减少包含T的子串长度
// 3，循环上述过程，找出包含T的最小子串

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function (s, t) {
  let l = 0 // 左指针
  let r = 0 // 右指针

  const need = new Map()
  for (let c of t) {
    need.set(c, need.has(c) ? need.get(c) + 1 : 1)
  }

  let needType = need.size
  while (r < s.length) {
    const c = s[r]
    if (need.has(c)) {
      need.set(c, need.get(c) - 1)
      if (need.get(c) === 0) {
        needType -= 1
      }
    }
    while (needType === 0) {
      const c2 = s[1]
      if (need.has(c2)) {
        need.set(c2, need.get(c2) + 1)
      }
      l += 1
    }
    r += 1
  }
};